public class O47 {
    public int maxValue(int[][] grid) {
        int dp[][] = new int[grid.length+1][grid[0].length+1];
        int re = grid[0][0];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                dp[i+1][j+1] = Math.max(dp[i][j+1],dp[i+1][j])+grid[i][j];
                re = Math.max(re,dp[i+1][j+1]);
            }
        }
        return re;
    }
}
